import com.sun.source.tree.Tree;

public class RBTree {

    static class TreeNode{
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public int val;
        public COLOR color;//节点的颜色

        public TreeNode(int val){
            this.val = val;
            //创建新的节点，颜色默认是红色；
            this.color = COLOR.RED;
        }
    }

    public TreeNode root;

    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if (root == null){
            root = node;
            root.color = COLOR.BLACK;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null){
            if (cur.val == val){
                return false;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else{
                parent = cur;
                cur = cur.right;
            }
        }
        if(parent.val > val){
            parent.left = node;
        }else {
            parent.right = node;
        }
        node.parent = parent;
        cur = node;

        //调整颜色；
        while(parent != null && parent.color == COLOR.RED){
            TreeNode grandParent = parent.parent;
            if(grandParent.left == parent){
                TreeNode uncle = grandParent.right;
                //情况一
                if (uncle != null && uncle.color == COLOR.RED){
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                    //接着向上调整
                    cur = grandParent;
                    parent = cur.parent;
                }else {
                    //uncle不存在或者uncle是黑色的
                    //情况三
                    if(cur == parent.right){
                        rotateLeft(parent);
                        TreeNode tmp = cur;
                        cur = parent;
                        parent =tmp;
                    }//情况三变为情况二

                    //情况二
                    rotateRight(grandParent);
                    parent.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                }
            }else {
                //grandParent.right == parent
                TreeNode uncle = grandParent.left;
                //情况一
                if (uncle != null && uncle.color == COLOR.RED){
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                    //接着向上调整
                    cur = grandParent;
                    parent = cur.parent;
                }else {
                    //uncle不存在或者uncle是黑色的
                    //情况三
                    if(cur == parent.left){
                        rotateRight(parent);
                        TreeNode tmp = cur;
                        cur = parent;
                        parent =tmp;
                    }//情况三变为情况二

                    //情况二
                    rotateLeft(grandParent);
                    parent.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                }
            }
        }
        //刚开始插入的时候，可能会导致根颜色变为红色，需要插入后手动修改为黑色
        root.color = COLOR.BLACK;
        return true;
      }

    /**
     * 右单旋
      * @param parent
     */
    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        TreeNode pParent = parent.parent;

        parent.left = subLR;
        subL.right = parent;
        parent.parent = subL;
        if (subLR != null){
            subLR.parent = parent;
        }

        if(parent == root){
            root = subLR;
            subL.parent = null;
        }else {
            if(pParent.left == parent){
                pParent.left = subL;
            }else {
                pParent.right = subL;
            }
            subLR.parent = pParent;
        }
    }

    /**
     *左单旋
     */
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;

        subR.left = parent;
        if(subRL != null) {
            subRL.parent = parent;
        }

        TreeNode pParent = parent.parent;
        parent.parent = subR;

        if(root == parent) {
            root = subR;
            root.parent = null;
        }else {
            if(pParent.left == parent) {
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
    }

    //中序遍历
    public void inorder(TreeNode root){
        if (root == null){
            return;
        }
        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
    }

    /**
     * 检验是否是红黑树
     */
    public boolean isRBTree(TreeNode root){
        if (root == null){
            return true;
        }

        if (root.color == COLOR.RED){
            System.out.println("违反了性质：根节点必须是黑色的");
            return false;
        }

        //最左边路径上的黑色节点个数
        int balckNum = 0;
        TreeNode cur = root;
        while(cur != null){
            if (cur.color == COLOR.BLACK){
                balckNum++;
            }
            cur = cur.left;
        }
        return checkRedColor(root) && checkBlackNum(root,0,balckNum);
    }

    /**
     * 检验每条路径上黑色的节点个数是否一致
     * @param root
     * @param pathBlackNum 每次递归的时候，计算黑色节点的个数
     * @param balckNum  事先计算好的某条路径上的黑色节点的个数
     * @return
     */
    private boolean checkBlackNum(TreeNode root, int pathBlackNum, int balckNum) {
        if(root == null){
            return true;
        }
        //遇到一个黑色节点，当前路径的pathBlackNum就++
        if(root.color == COLOR.BLACK){
            pathBlackNum++;
        }

        if(root.left == null && root.right == null){
            if (pathBlackNum != balckNum){
                System.out.println("违反了性质：每条路径上黑色的节点个数是不一样的");
                return false;
            }
        }
        return checkBlackNum(root.left,pathBlackNum,balckNum)
                && checkBlackNum(root.right,pathBlackNum,balckNum);
    }

    /**
     * 检验是否存在连续两个红色节点
     * @param cur
     * @return
     */
    private boolean checkRedColor(TreeNode cur) {
        if (cur == null){
            return true;
        }
        if (cur.color == COLOR.RED && cur.parent.color == COLOR.RED){
            System.out.println("违反了性质：连续出现了两个红色的节点");
            return false;
        }

        return checkRedColor(cur.left) && checkRedColor(cur.right);
    }
}
